package com.bigshen.algorithm.jBfs.solution01NumberOfIslands;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 200. Number of Islands  小岛问题、岛屿数量
 * Given an m x n 2d grid map of '1's (land) and '0's (water), return the number of islands.
 *
 * An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
 *
 *  
 *
 * Example 1:
 *
 * Input: grid = [
 *   ["1","1","1","1","0"],
 *   ["1","1","0","1","0"],
 *   ["1","1","0","0","0"],
 *   ["0","0","0","0","0"]
 * ]
 * Output: 1
 *
 * Example 2:
 * Input: grid = [
 *   ["1","1","0","0","0"],
 *   ["1","1","0","0","0"],
 *   ["0","0","1","0","0"],
 *   ["0","0","0","1","1"]
 * ]
 * Output: 3
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/number-of-islands
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public int numIslands(char[][] grid) {
        if (null == grid || grid.length == 0) {
            return 0;
        }
        if (null == grid[0] || grid[0].length == 0) {
            return 0;
        }
        int total = 0;
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i ++) {
            for (int j = 0; j < grid[0].length; j ++) {
                // 发现没有访问过得陆地，记录并为兄弟节点打标机
                if (grid[i][j] == '1' && !visited[i][j]) {
                    bfsTagBrother(grid, i, j, visited);
                    total ++;
                }
            }
        }
        return total;
    }

    // 根据一个坐标，找出上、下、左、右 兄弟节点标记
    private void bfsTagBrother(char[][] grid, int i, int j, boolean[][] visited) {
        int[] xArray = {1, -1, 0, 0};
        int[] yArray = {0, 0, 1, -1};
        // 标记已访问过
        visited[i][j] = true;
        Queue<Integer> xQueue = new LinkedList();
        Queue<Integer> yQueue = new LinkedList();
        xQueue.offer(i);
        yQueue.offer(j);
        while (!xQueue.isEmpty()) {
            int x = xQueue.poll();
            int y = yQueue.poll();
            // 找出连接的兄弟节点并标记
            for (int k = 0; k < xArray.length; k ++) {
                // 上下左右 兄弟节点新坐标
                int newX = x + xArray[k];
                int newY = y + yArray[k];
                if (newX > -1 && newX < grid.length && newY > -1 && newY < grid[0].length
                        && grid[newX][newY] == '1' && !visited[newX][newY]) {
                    xQueue.offer(newX);
                    yQueue.offer(newY);
                    visited[newX][newY] = true;
                }
            }

        }
    }
}